package leetcode;


public class MaximumProduct {

	public static void main(String[] args) {
		MaximumProduct product = new MaximumProduct();
		int[] nums = { -3, -4, -5, 1};
		System.out.println(product.maxProduct3(nums));
	}
	//obviously，it's O(n^2) time and O(n^2) space
	//TLE 
	public int maxProduct(int[] nums) {
		if (nums == null || nums.length <= 0) {
			return 0;
		}
		int[][] res = new int[nums.length + 1][nums.length + 1];
		for (int i = 0; i < res.length; i++) {
			for (int j = 0; j < res[0].length; j++) {
				res[i][j] = 1;
			}
		}
		int max = nums[0];
		for (int i = 1; i <= nums.length; i++) {
			for (int j = i; j <= nums.length; j++) {
				res[i][j] = res[i][j - 1] * nums[j - 1];
				if (res[i][j] > max) {
					max = res[i][j];
				}
			}
		}
		for (int i = 0; i < res.length; i++) {
			for (int j = 0; j < res[0].length; j++) {
				System.out.print(" " + res[i][j]);
			}
			System.out.println();
		}
		return max;
	}
	
	//自己写的，是错的，-3， -4， -5 ，1的时候得出的结果是12
	public int maxProduct2(int[] nums){
		int left = Integer.MIN_VALUE;
		int product = 1;
		int max = nums[0];
		for(int i = 0; i < nums.length; i++){
			if(nums[i] < 0 ){
				if(left == Integer.MIN_VALUE){
					left = product;  //用left将product保存起来
					product = nums[i];
					continue;
				}
				product = product * left * nums[i];
				left = Integer.MIN_VALUE;
			}else{
				product *= nums[i];
			}
			if(product > max){
				max = product;
			}
		}
		return max;
	}
	//one Question, why product is difficult, because there may be negative
	//why negative affect we solve the problem, because negative * negative is positive
	//so we don't know what is the best choice to get negative
	//think about, because there it's negative, so maybe change the thing,
	//we can keep max and min, while negative * min is max, and positive * max is max
	
	public int maxProduct3(int[] nums){
		if(nums == null || nums.length <= 0){
			return 0;
		}
		int max = nums[0], min = nums[0];
		int temp;  //用于交换
		int res = nums[0];
		for(int i = 1; i < nums.length; i++){
			if(nums[i] < 0){
				temp = max;
				max = min;
				min = temp;
			}
			max = Math.max(nums[i], max * nums[i]);  //比如max为负的时候 -3 ， 2 ， 4， -1
			min = Math.min(nums[i], min * nums[i]); //注意，是子数组, 肯定是连续的
			res = Math.max(res, max);
		}
		return res;
	}
}
